23.8 KB · ⇊ 7 parts · ⤓ Micron 23.8 KB · ⤓ HTML 226.1 KB

top

Der QZ-Algorithmus oder die QZ-Faktorisierung ist ein numerisches Verfahren zur Lösung des verallgemeinerten Eigenwertproblems.

A x = λ λ B x {\displaystyle Ax=\lambda Bx^{\,}} , mit A , B ∈ ∈ R n × × n {\displaystyle A,B\in \mathbb {R} ^{n\times n}} bzw. A , B ∈ ∈ C n × × n {\displaystyle A,B\in \mathbb {C} ^{n\times n}}

Das verallgemeinerte Eigenwertproblem ist äquivalent zum Eigenwertproblem A B − − 1 y = λ λ y {\displaystyle AB^{-1}y=\lambda y} , wobei y = B x {\displaystyle y=Bx} und B {\displaystyle B} invertierbar sein muss. Es wird jedoch nicht explizit die Matrix B − − 1 {\displaystyle B^{-1}} berechnet, um die Kondition des Problems nicht zu verschlechtern, sondern A {\displaystyle A} und B {\displaystyle B} werden simultan durch Ähnlichkeitstransformationen (Givens-Rotationen und Householder-Spiegelungen) in verallgemeinerte Schurform gebracht.

Gegeben ist ein Matrixbüschel A − − λ λ B {\displaystyle A-\lambda B} . Gesucht sind orthogonale Matrizen Q {\displaystyle Q} und Z {\displaystyle Z} , so dass Q T ( A − − λ λ B ) Z = T − − λ λ S {\displaystyle Q^{T}(A-\lambda B)Z=T-\lambda S} von verallgemeinerter Schurform ist, d. h. T {\displaystyle T} ist von quasi-oberer Dreiecksform und S {\displaystyle S} ist von oberer Dreiecksform. Im Fall A , B ∈ ∈ C n × × n {\displaystyle A,B\in \mathbb {C} ^{n\times n}} ist T {\displaystyle T} stets von oberer Dreiecksform. Aus der verallgemeinerten Schurform lassen sich dann die Eigenwerte und aus Q {\displaystyle Q} und Z {\displaystyle Z} ( A , B ) {\displaystyle (A,B)} -invariante Unterräume des Matrixbüschels A − − λ λ B {\displaystyle A-\lambda B} bestimmen.

• Vortransformation

• QZ-Algorithmus mit impliziten Shifts

• Wahl der Shifts

• Der implizite QZ-Schritt

• Bestimmung der Eigenwerte

• Literatur

Ziel dieses Schrittes ist es, die Matrix A {\displaystyle A} durch orthogonale Transformationen auf obere Hessenbergform und die Matrix B {\displaystyle B} auf obere Dreiecksform zu bringen. Durch n − − 1 {\displaystyle n-1} Householder-Spiegelungen von links wird B {\displaystyle B} auf obere Dreiecksform transformiert. Wendet man die gleichen Transformationen gleichzeitig auf A {\displaystyle A} an, ergibt sich (Veranschaulichung an einem Beispiel der Größe (4,4)): A = ( ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ) , B = ( ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ 0 ∗ ∗ ∗ ∗ ∗ ∗ 0 0 ∗ ∗ ∗ ∗ 0 0 0 ∗ ∗ ) {\displaystyle A={\begin{pmatrix}*&*&*&*\\{*}&*&*&*\\{*}&*&*&*\\{*}&*&*&*\end{pmatrix}},B={\begin{pmatrix}*&*&*&*\\0&*&*&*\\0&0&*&*\\0&0&0&*\end{pmatrix}}} .

Man finde nun eine Givens-Rotation, die von links angewendet auf A folgende Matrix ergibt: A = ( ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ 0 ∗ ∗ ∗ ∗ ∗ ∗ ) {\displaystyle A={\begin{pmatrix}*&*&*&*\\{*}&*&*&*\\{*}&*&*&*\\0&*&*&*\end{pmatrix}}} . Damit erhält man für B = ( ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ 0 ∗ ∗ ∗ ∗ ∗ ∗ 0 0 ∗ ∗ ∗ ∗ 0 0 ∗ ∗ ∗ ∗ ) {\displaystyle B={\begin{pmatrix}*&*&*&*\\0&*&*&*\\0&0&*&*\\0&0&*&*\end{pmatrix}}} .

Durch Anwendung einer Givens-Rotation von rechts kann die obere Dreiecksform von B {\displaystyle B} wiederhergestellt werden, ohne die Null an der linken unteren Position von A zu zerstören: A = ( ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ 0 ∗ ∗ ∗ ∗ ∗ ∗ ) , B = ( ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ 0 ∗ ∗ ∗ ∗ ∗ ∗ 0 0 ∗ ∗ ∗ ∗ 0 0 0 ∗ ∗ ) {\displaystyle A={\begin{pmatrix}*&*&*&*\\{*}&*&*&*\\{*}&*&*&*\\0&*&*&*\end{pmatrix}},B={\begin{pmatrix}*&*&*&*\\0&*&*&*\\0&0&*&*\\0&0&0&*\end{pmatrix}}} .

Durch analoges spaltenweises Erzeugen von Nullen in A {\displaystyle A} erhält man eine obere Hessenbergmatrix:

1. A = ( ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ 0 ∗ ∗ ∗ ∗ ∗ ∗ 0 ∗ ∗ ∗ ∗ ∗ ∗ ) , B = ( ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ 0 ∗ ∗ ∗ ∗ ∗ ∗ 0 ∗ ∗ ∗ ∗ ∗ ∗ 0 0 0 ∗ ∗ ) {\displaystyle A={\begin{pmatrix}*&*&*&*\\{*}&*&*&*\\0&*&*&*\\0&*&*&*\end{pmatrix}},B={\begin{pmatrix}*&*&*&*\\0&*&*&*\\0&*&*&*\\0&0&0&*\end{pmatrix}}}

2. A = ( ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ 0 ∗ ∗ ∗ ∗ ∗ ∗ 0 ∗ ∗ ∗ ∗ ∗ ∗ ) , B = ( ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ 0 ∗ ∗ ∗ ∗ ∗ ∗ 0 0 ∗ ∗ ∗ ∗ 0 0 0 ∗ ∗ ) {\displaystyle A={\begin{pmatrix}*&*&*&*\\{*}&*&*&*\\0&*&*&*\\0&*&*&*\end{pmatrix}},B={\begin{pmatrix}*&*&*&*\\0&*&*&*\\0&0&*&*\\0&0&0&*\end{pmatrix}}}

3. A = ( ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ 0 ∗ ∗ ∗ ∗ ∗ ∗ 0 0 ∗ ∗ ∗ ∗ ) , B = ( ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ 0 ∗ ∗ ∗ ∗ ∗ ∗ 0 0 ∗ ∗ ∗ ∗ 0 0 ∗ ∗ ∗ ∗ ) {\displaystyle A={\begin{pmatrix}*&*&*&*\\{*}&*&*&*\\0&*&*&*\\0&0&*&*\end{pmatrix}},B={\begin{pmatrix}*&*&*&*\\0&*&*&*\\0&0&*&*\\0&0&*&*\end{pmatrix}}}

4. A = ( ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ 0 ∗ ∗ ∗ ∗ ∗ ∗ 0 0 ∗ ∗ ∗ ∗ ) , B = ( ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ 0 ∗ ∗ ∗ ∗ ∗ ∗ 0 0 ∗ ∗ ∗ ∗ 0 0 0 ∗ ∗ ) {\displaystyle A={\begin{pmatrix}*&*&*&*\\{*}&*&*&*\\0&*&*&*\\0&0&*&*\end{pmatrix}},B={\begin{pmatrix}*&*&*&*\\0&*&*&*\\0&0&*&*\\0&0&0&*\end{pmatrix}}} .

Falls ( A , B ) {\displaystyle (A,B)} -invariante Unterräume berechnet werden sollen, so ist es notwendig, das Produkt der Transformationsmatrizen, die jeweils von links auf A {\displaystyle A} und B {\displaystyle B} angewendet werden, in einer Matrix Q {\displaystyle Q} und das Produkt der Transformationsmatrizen, die von rechts angewendet werden, in einer Matrix Z {\displaystyle Z} zu speichern.

1. q := 0 {\displaystyle q:=0}

2. while q < n {\displaystyle q<n} do

3. Bestimme alle j ∈ ∈ { 1 , ⋯ ⋯ , n − − 1 } {\displaystyle j\in \{1,\cdots ,n-1\}} mit | a j + 1 , j | ≤ ≤ ε ε ( | a j , j | + | a j + 1 , j + 1 | ) {\displaystyle |a_{j+1,j}|\leq \varepsilon (|a_{j,j}|+|a_{j+1,j+1}|)} . Für diese j {\displaystyle j} setze a j , j + 1 = 0 {\displaystyle a_{j,j+1}=0} .

4. Deflation: Finde minimales p {\displaystyle p} und maximales q {\displaystyle q} mit p , q ∈ ∈ { 1 , ⋯ ⋯ , n } {\displaystyle p,q\in \{1,\cdots ,n\}} und definiere m := n − − p − − q {\displaystyle m:=n-p-q} , so dass gilt: A = ( A 11 A 12 A 13 0 A 22 A 23 0 0 A 33 ) {\displaystyle A={\begin{pmatrix}A_{11}&A_{12}&A_{13}\\0&A_{22}&A_{23}\\0&0&A_{33}\end{pmatrix}}} , wobei A 11 ∈ ∈ R p × × p , A 22 ∈ ∈ R m × × m , A 33 ∈ ∈ R q × × q {\displaystyle A_{11}\in \mathbb {R} ^{p\times p},A_{22}\in \mathbb {R} ^{m\times m},A_{33}\in \mathbb {R} ^{q\times q}} und A 11 {\displaystyle A_{11}} von oberer Hessenbergform, A 22 {\displaystyle A_{22}} von unreduzierter oberer Hessenbergform und A 33 {\displaystyle A_{33}} von quasi-oberer Dreiecksform ist.

5. Partitioniere B {\displaystyle B} wie A {\displaystyle A} , d. h. B = ( B 11 B 12 B 13 0 B 22 B 23 0 0 B 33 ) {\displaystyle B={\begin{pmatrix}B_{11}&B_{12}&B_{13}\\0&B_{22}&B_{23}\\0&0&B_{33}\end{pmatrix}}} , wobei B 11 ∈ ∈ R p × × p , B 22 ∈ ∈ R m × × m , B 33 ∈ ∈ R q × × q {\displaystyle B_{11}\in \mathbb {R} ^{p\times p},B_{22}\in \mathbb {R} ^{m\times m},B_{33}\in \mathbb {R} ^{q\times q}} obere Dreiecksmatrizen sind.

6. Bringe A 33 {\displaystyle A_{33}} in obere Schurform: Finde orthogonale Q 33 , Z 33 {\displaystyle Q_{33},Z_{33}} so, dass A 33 := Q 33 T A 33 Z 33 {\displaystyle A_{33}:=Q_{33}^{T}A_{33}Z_{33}} in Schurform und B 33 := Q 33 T B 33 Z 33 {\displaystyle B_{33}:=Q_{33}^{T}B_{33}Z_{33}} obere Dreiecksmatrix ist.

Falls erforderlich: Aufdatieren von Q {\displaystyle Q} und Z {\displaystyle Z} : Q := Q d i a g ( I p , I m , Q 33 ) {\displaystyle Q:=Q\mathrm {diag} (I_{p},I_{m},Q_{33})} , Z := Z d i a g ( I p , I m , Z 33 ) {\displaystyle Z:=Z\mathrm {diag} (I_{p},I_{m},Z_{33})} .

7. if q < n {\displaystyle q<n} :

if d e t ( B 22 ) = 0 {\displaystyle det(B_{22})=0}

Transformiere mithilfe einer Givens-Rotation von rechts a n − − q , n − − q − − 1 = 0 {\displaystyle a_{n-q,n-q-1}=0} , um die Rang-Defizienz von B 22 {\displaystyle B_{22}} auf B 33 {\displaystyle B_{33}} zu verschieben. Durch die Annullierung von a n − − q , n − − q − − 1 {\displaystyle a_{n-q,n-q-1}} ist A 22 {\displaystyle A_{22}} keine unreduzierte Hessenbergmatrix mehr, somit wird q {\displaystyle q} erhöht und es besteht die Möglichkeit, dass B 22 {\displaystyle B_{22}} in der neuen Partitionierung regulär ist.

else

Führe einen impliziten QZ-Schritt für A 22 , B 22 {\displaystyle A_{22},B_{22}} aus: A 22 := Q 22 T A 22 Z 22 , B 22 := Q 22 T B 22 Z 22 {\displaystyle A_{22}:=Q_{22}^{T}A_{22}Z_{22},\quad {B_{22}}:=Q_{22}^{T}{B_{22}}Z_{22}} .

end if

8. end if

9. Bestimme Shifts a , b {\displaystyle a,b} als Eigenwerte von ( a m − − 1 , m − − 1 a m − − 1 , m a m , m − − 1 a m , m ) ( b m − − 1 , m − − 1 b m − − 1 , m 0 b m , m ) − − 1 {\displaystyle {\begin{pmatrix}a_{m-1,m-1}&a_{m-1,m}\\a_{m,m-1}&a_{m,m}\end{pmatrix}}{\begin{pmatrix}b_{m-1,m-1}&b_{m-1,m}\\0&b_{m,m}\end{pmatrix}}^{-1}}

10. Bestimme ( A 22 B 22 − − 1 − − a I ) ( A 22 B 22 − − 1 − − b I ) e 1 = ( α α β β γ γ 0 ⋮ ⋮ 0 ) {\displaystyle (A_{22}B_{22}^{-1}-aI)(A_{22}B_{22}^{-1}-bI)e_{1}={\begin{pmatrix}\alpha \\\beta \\\gamma \\0\\\vdots \\0\end{pmatrix}}}

11. Finde orthogonales Q 1 {\displaystyle Q_{1}} mit Q 1 T ( α α β β γ γ ) = ( ∗ ∗ 0 0 ) {\displaystyle Q_{1}^{T}{\begin{pmatrix}\alpha \\\beta \\\gamma \end{pmatrix}}={\begin{pmatrix}*\\0\\0\end{pmatrix}}}

Für B 22 {\displaystyle B_{22}} folgt nun: ( Q 1 T 0 0 I m − − 3 ) B 22 = ( ∗ ∗ ∗ ∗ ∗ ∗ ⋯ ⋯ ⋯ ⋯ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ⋯ ⋯ ⋯ ⋯ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ⋯ ⋯ ⋯ ⋯ ∗ ∗ 0 0 0 ⋱ ⋱ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋱ ⋮ ⋮ 0 0 0 ⋯ ⋯ ⋯ ⋯ ∗ ∗ ) {\displaystyle {\begin{pmatrix}Q_{1}^{T}&0\\0&I_{m-3}\end{pmatrix}}B_{22}={\begin{pmatrix}*&*&*&\cdots &\cdots &*\\{*}&*&*&\cdots &\cdots &*\\{*}&*&*&\cdots &\cdots &*\\0&0&0&\ddots &&\vdots \\\vdots &\vdots &\vdots &&\ddots &\vdots \\0&0&0&\cdots &\cdots &*\end{pmatrix}}} .

Ziel ist es nun, die Dreiecksgestalt von B 22 {\displaystyle B_{22}} durch orthogonale Transformationen (Householder-Spiegelungen) von rechts wiederherzustellen:

12. Finde orthogonales Z 1 ∈ ∈ R 3 × × 3 {\displaystyle Z_{1}\in \mathbb {R} ^{3\times 3}} mit B 22 d i a g ( Z 1 , I m − − 3 ) = ( ∗ ∗ ∗ ∗ ∗ ∗ ⋯ ⋯ ⋯ ⋯ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ⋯ ⋯ ⋯ ⋯ ∗ ∗ 0 0 ∗ ∗ ⋯ ⋯ ⋯ ⋯ ∗ ∗ 0 0 0 ⋱ ⋱ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋱ ⋮ ⋮ 0 0 0 ⋯ ⋯ ⋯ ⋯ ∗ ∗ ) {\displaystyle B_{22}\mathrm {diag} (Z_{1},I_{m-3})={\begin{pmatrix}*&*&*&\cdots &\cdots &*\\{*}&*&*&\cdots &\cdots &*\\0&0&*&\cdots &\cdots &*\\0&0&0&\ddots &&\vdots \\\vdots &\vdots &\vdots &&\ddots &\vdots \\0&0&0&\cdots &\cdots &*\end{pmatrix}}} . Finde dann orthogonales Z 1 ′ ∈ ∈ R 2 × × 2 {\displaystyle Z_{1}'\in \mathbb {R} ^{2\times 2}} , so dass

B 22 d i a g ( Z 1 , I m − − 3 ) d i a g ( Z 1 ′ , I m − − 2 ) = ( ∗ ∗ ∗ ∗ ∗ ∗ ⋯ ⋯ ⋯ ⋯ ∗ ∗ 0 ∗ ∗ ∗ ∗ ⋯ ⋯ ⋯ ⋯ ∗ ∗ 0 0 ∗ ∗ ⋯ ⋯ ⋯ ⋯ ∗ ∗ 0 0 0 ⋱ ⋱ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋱ ⋮ ⋮ 0 0 0 ⋯ ⋯ ⋯ ⋯ ∗ ∗ ) {\displaystyle B_{22}\mathrm {diag} (Z_{1},I_{m-3})\mathrm {diag} (Z_{1}',I_{m-2})={\begin{pmatrix}*&*&*&\cdots &\cdots &*\\0&*&*&\cdots &\cdots &*\\0&0&*&\cdots &\cdots &*\\0&0&0&\ddots &&\vdots \\\vdots &\vdots &\vdots &&\ddots &\vdots \\0&0&0&\cdots &\cdots &*\end{pmatrix}}} .

Für A 22 {\displaystyle A_{22}} ergibt sich nun: A ~ ~ 22 := A 22 d i a g ( Z 1 , I m − − 3 ) d i a g ( Z 1 ′ , I m − − 2 ) = ( ∗ ∗ ∗ ∗ ∗ ∗ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ∗ ∗ 0 0 0 ⋱ ⋱ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋱ ⋮ ⋮ 0 0 0 ⋯ ⋯ 0 ∗ ∗ ∗ ∗ ) {\displaystyle {\tilde {A}}_{22}:={A_{22}}\mathrm {diag} (Z_{1},I_{m-3})\mathrm {diag} (Z'_{1},I_{m-2})={\begin{pmatrix}*&*&*&\cdots &\cdots &\cdots &*\\{*}&*&*&\cdots &\cdots &\cdots &*\\{*}&*&*&\cdots &\cdots &\cdots &*\\{*}&*&*&\cdots &\cdots &\cdots &*\\0&0&0&\ddots &&&\vdots \\\vdots &\vdots &\vdots &&\ddots &&\vdots \\0&0&0&\cdots &0&*&*\end{pmatrix}}} . D.h., die Hessenbergstruktur von A 22 {\displaystyle A_{22}} ist durch einen unerwünschten 2x2 „Buckel“ zerstört.

13. Dieser Buckel kann durch elementäre, orthogonale Transformationen (z. B. Householder-Spiegelungen) von links eliminiert werden. Finde also orthogonales Q 1 ″ ∈ ∈ R 3 × × 3 {\displaystyle Q''_{1}\in \mathbb {R} ^{3\times 3}} , Q 1 ′ ∈ ∈ R 3 × × 3 {\displaystyle Q_{1}'\in \mathbb {R} ^{3\times 3}} mit

d i a g ( 1 , Q 1 ′ , I m − − 4 ) T d i a g ( I 2 , Q 1 ″ , I m − − 5 ) T A ~ ~ 22 = ( ∗ ∗ ∗ ∗ ∗ ∗ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ∗ ∗ 0 ∗ ∗ ∗ ∗ ⋱ ⋱ ⋯ ⋯ ⋯ ⋯ ∗ ∗ 0 0 ∗ ∗ ⋱ ⋱ ⋯ ⋯ ⋯ ⋯ ∗ ∗ 0 0 0 ∗ ∗ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋱ ⋮ ⋮ 0 0 0 ⋯ ⋯ 0 ∗ ∗ ∗ ∗ ) {\displaystyle \mathrm {diag} (1,Q'_{1},I_{m-4})^{T}\mathrm {diag} (I_{2},Q''_{1},I_{m-5})^{T}{{\tilde {A}}_{22}}={\begin{pmatrix}*&*&*&\cdots &\cdots &\cdots &*\\*&*&*&\cdots &\cdots &\cdots &*\\0&*&*&\ddots &\cdots &\cdots &*\\0&0&*&\ddots &\cdots &\cdots &*\\0&0&0&*&&\vdots \\\vdots &\vdots &\vdots &&\ddots &&\vdots \\0&0&0&\cdots &0&*&*\end{pmatrix}}} . Es werden also nacheinander die Vektoren ( a 21 a 31 a 41 ) {\displaystyle {\begin{pmatrix}a_{21}\\a_{31}\\a_{41}\end{pmatrix}}} und ( a 32 a 42 a 52 ) {\displaystyle {\begin{pmatrix}a_{32}\\a_{42}\\a_{52}\end{pmatrix}}} auf ( ∗ ∗ 0 0 ) {\displaystyle {\begin{pmatrix}*\\0\\0\end{pmatrix}}} transformiert.

Die Anwendung der Transformation auf B ~ ~ 22 {\displaystyle {\tilde {B}}_{22}} von links ergibt jedoch

d i a g ( 1 , Q 1 ′ , I m − − 4 ) T d i a g ( I 2 , Q 1 ″ , I m − − 5 ) T B ~ ~ 22 = ( ∗ ∗ ∗ ∗ ∗ ∗ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ∗ ∗ 0 ∗ ∗ ∗ ∗ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ∗ ∗ 0 ∗ ∗ ∗ ∗ ⋱ ⋱ ⋯ ⋯ ⋯ ⋯ ∗ ∗ 0 ∗ ∗ ∗ ∗ ∗ ∗ ⋱ ⋱ ⋯ ⋯ ∗ ∗ 0 0 0 0 ∗ ∗ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋱ ⋮ ⋮ 0 0 0 ⋯ ⋯ 0 0 ∗ ∗ ) {\displaystyle \mathrm {diag} (1,Q'_{1},I_{m-4})^{T}\mathrm {diag} (I_{2},Q''_{1},I_{m-5})^{T}{{\tilde {B}}_{22}}={\begin{pmatrix}*&*&*&\cdots &\cdots &\cdots &*\\0&*&*&\cdots &\cdots &\cdots &*\\0&*&*&\ddots &\cdots &\cdots &*\\0&*&*&*&\ddots &\cdots &*\\0&0&0&0&*&\vdots \\\vdots &\vdots &\vdots &&\ddots &&\vdots \\0&0&0&\cdots &0&0&*\end{pmatrix}}} , d. h. ein Buckel ist jetzt eine Position tiefer entlang der Diagonalen entstanden.

14. Man wiederhole die Schritte 11–13 so lange, bis A 22 {\displaystyle A_{22}} wieder in oberer Hessenberg- und B 22 {\displaystyle B_{22}} wieder in oberer Dreieckstruktur vorliegt. Diesen Prozess bezeichnet man, analog zum QR-Algorithmus, auch als „Buckel-Jagen“ oder „Bulge-Chasing“. Die Eliminierung eines Buckels in B 22 {\displaystyle B_{22}} an der Diagonalposition j mit Transformationen von links führt zu einem Buckel an der entsprechenden Position in A 22 {\displaystyle A_{22}} . Wird dieser Buckel mit Transformationen von rechts eliminiert, führt das zu einem Buckel in B 22 {\displaystyle B_{22}} an der Diagonalposition j+1 usw.

15. Nach m − − 2 {\displaystyle m-2} Schritten wird das Ziel erreicht und es ergibt sich Q 22 T = d i a g ( Q 1 , I m − − 3 ) T d i a g ( 1 , Q 1 ′ , I m − − 4 ) T d i a g ( I 2 , Q 1 ″ , I m − − 5 ) T ⋯ ⋯ d i a g ( I m − − 3 , Q m − − 2 ) T {\displaystyle Q_{22}^{T}=\mathrm {diag} (Q_{1},I_{m-3})^{T}\mathrm {diag} (1,Q'_{1},I_{m-4})^{T}\mathrm {diag} (I_{2},Q_{1}'',I_{m-5})^{T}\cdots \mathrm {diag} (I_{m-3},Q_{m-2})^{T}} . Analog erhält man

Z 22 = d i a g ( Z 1 , I m − − 3 ) d i a g ( Z 1 ′ , I m − − 2 ) ⋯ ⋯ d i a g ( I m − − 2 , Z m − − 2 ) d i a g ( I m − − 2 , Z m − − 2 ′ ) {\displaystyle Z_{22}=\mathrm {diag} (Z_{1},I_{m-3})\mathrm {diag} (Z_{1}',I_{m-2})\cdots \mathrm {diag} (I_{m-2},Z_{m-2})\mathrm {diag} (I_{m-2},Z_{m-2}')} .

Falls ( A , B ) {\displaystyle (A,B)} -invarianten Unterräume benötigt werden, ist es notwendig die Matrizen Q {\displaystyle {Q}} und Z {\displaystyle Z} aufzudatieren: Q := Q d i a g ( I p , Q 22 , I q ) {\displaystyle Q:=Q\mathrm {diag} (I_{p},Q_{22},I_{q})} , Z := Z d i a g ( I p , Z 22 , I q ) {\displaystyle Z:=Z\mathrm {diag} (I_{p},Z_{22},I_{q})}

16. end while

In den meisten Fällen konvergiert ( A , B ) {\displaystyle (A,B)} im QZ-Algorithmus gegen seine verallgemeinerte, reelle Schur-Form. Für skalare Diagonalblöcke in A gilt λ λ i = a i i b i i : b i i ≠ ≠ 0 {\displaystyle \lambda _{i}={\frac {a_{ii}}{b_{ii}}}:b_{ii}\neq 0} und λ λ i = ∞ ∞ {\displaystyle \lambda _{i}=\infty } falls b i i = 0 {\displaystyle b_{ii}=0} . Falls ein i {\displaystyle i} existiert, für das a i i = b i i = 0 {\displaystyle a_{ii}=b_{ii}=0} ist, so ist Λ Λ ( A , B ) = C {\displaystyle \Lambda (A,B)=\mathbb {C} } . 2 × × 2 {\displaystyle 2\times 2} Diagonalblöcke von A {\displaystyle A} beziehen sich (analog zum QR-Algorithmus) auf Paare komplex konjugierter Eigenwerte λ λ , λ λ ¯ ¯ = Λ Λ ( ( a i i a i , i + 1 a i + 1 , i a i + 1 , i + 1 ) , ( b i i b i , i + 1 0 b i + 1 , i + 1 ) ) {\displaystyle \lambda ,{\overline {\lambda }}=\Lambda \left({\begin{pmatrix}a_{ii}&a_{i,i+1}\\a_{i+1,i}&a_{i+1,i+1}\end{pmatrix}},{\begin{pmatrix}b_{ii}&b_{i,i+1}\\0&b_{i+1,i+1}\end{pmatrix}}\right)} .

• Gene H. Golub, Charles F. Van Loan: Matrix Computations. Johns Hopkins University Press, 1996, ISBN 0-8018-5414-8.

• G. W. Stewart: Matrix Algorithms. Band II: Eigensystems. SIAM 2001, ISBN 0-89871-503-2.